package com.spirng.leetcode.day03;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ThreeSum {
    public static void main(String[] args) {
        threeSum(new int[]{-2,0,3,-1,4,0,3,4,1,1,1,-3,-5,4,0});
    }
    public static List<List<Integer>> threeSum(int[] nums) {
        List list=new ArrayList<List<Integer>>();
        int left;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }else {
                int right=nums.length-1;
                left=i+1;
                while (left<right){
                    List result=new ArrayList<Integer>();
                    if (nums[i]+nums[left]+nums[right]>0){
                        right--;
                    } else if (nums[i] + nums[left] + nums[right] < 0) {
                        left++;
                    }else {
                        while (left< nums.length-1&&nums[left]==nums[left+1]) left++;
                        while (right>0&&nums[right]==nums[right-1]) right--;
                        add(nums[i],nums[left],nums[right],result);
                        list.add(result);
                        left++;
                        right--;
                    }
                }
            }
        }
        return list;
    }
    public static void add(int i,int j ,int z,List<Integer> list){
        list.add(i);
        list.add(j);
        list.add(z);
    }
}
